package com.hy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * author: Mr.Du
 * Date: 2023/12/6
 * Time: 10:23
 */
public class CreateTree {

    public TreeNode constructTree(int n) {
        if (n <= 0) {
            return null;
        }

        // 创建节点数组
        TreeNode[] nodes = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(i);
        }

        // 构建二叉树
        for (int i = 0; i < n; i++) {
            if (2 * i + 1 < n) {
                nodes[i].left = nodes[2 * i + 1];
            }
            if (2 * i + 2 < n) {
                nodes[i].right = nodes[2 * i + 2];
            }
        }

        // 返回根节点
        return nodes[0];
    }

    public static void main(String[] args) {
        CreateTree createTree = new CreateTree();
        TreeNode root = createTree.constructTree(7);
        createTree.pre(root);
        System.out.println();
        createTree.cengxu(root);
        int kthAncestor = createTree.getKthAncestor(root, 3, 1);
        System.out.println(kthAncestor);
    }

    public void pre(TreeNode root){
        if(root == null) return;
        System.out.print(root.val + " ");
        pre(root.left);
        pre(root.right);
    }

    public void cengxu(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            while(sz != 0){
                TreeNode tmp = queue.poll();
                System.out.print(tmp.val + " ");
                if(tmp.left != null) queue.offer(tmp.left);
                if(tmp.right != null) queue.offer(tmp.right);
                sz--;
            }
            System.out.println();
        }
    }

    public int getKthAncestor(TreeNode root, int node, int k) {
        TreeNode res = findKthAncestor(root, node, k);
        return  res == null?-1:res.val;
    }
    public TreeNode findKthAncestor(TreeNode root, int node, int k) {
        if (root == null) {
            return null;
        }

        if (root.val == node || k == 0) {
            return root;
        }

        TreeNode left = findKthAncestor(root.left, node, k);
        TreeNode right = findKthAncestor(root.right, node, k);

        if (left != null || right != null) {
            return root;
        }

        return null;
    }
}
